Search results for "Competitive analysis"

showing 3 items of 3 documents

Online Scheduling of Task Graphs on Hybrid Platforms

2018

Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous \(4\sqrt{m/k}\)-competitive online algorithm [2], where m is the number of CPUs and k the number of GPUs (\(m\ge k\)). We prove that no online algorithm can have a competitive ratio …

020203 distributed computingCompetitive analysisonline algorithmsComputer scienceHeuristicSchedulingSymmetric multiprocessor system02 engineering and technologyParallel computingUpper and lower boundsheterogeneous computingGraph020202 computer hardware & architectureScheduling (computing)task graphs0202 electrical engineering electronic engineering information engineeringOnline algorithm[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC]
researchProduct

Online Scheduling of Task Graphs on Heterogeneous Platforms

2020

Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…

Discrete mathematics[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]020203 distributed computingScheduleCompetitive analysisComputer scienceHeuristicSchedulingOnline algorithmsProcessor schedulingSymmetric multiprocessor system02 engineering and technologyUpper and lower boundsGraphScheduling (computing)Computational Theory and MathematicsHardware and ArchitectureSignal Processing0202 electrical engineering electronic engineering information engineeringTask analysisTask graphsHeterogeneous computingOnline algorithm[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC]
researchProduct

Two-way quantum and classical machines with small memory for online minimization problems

2019

We consider online algorithms. Typically the model is investigated with respect to competitive ratio. In this paper, we explore algorithms with small memory. We investigate two-way automata as a model for online algorithms with restricted memory. We focus on quantum and classical online algorithms. We show that there are problems that can be better solved by two-way automata with quantum and classical states than classical two-way automata in the case of sublogarithmic memory (sublinear size).

Theoretical computer scienceComputational complexity theoryCompetitive analysisSublinear functionComputer scienceOnline algorithmFocus (optics)QuantumAutomatonQuantum computerInternational Conference on Micro- and Nano-Electronics 2018
researchProduct